import java.awt.Polygon;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.util.LinkedList;
class Global {
    public static int SAFETY_MARGIN = 0;		// safety margin along obstacles
    public static int SAFETY_MARGIN2 = 3;               // extra safety margin for actual points
    public static double SCALING = 1;			// scaling for visualization
    public static double X_TRANS = 250;			// translations for visualization
    public static double Y_TRANS = 200;
    public static int VISU_HEIGHT = 300;		// visualization height and weight
    public static int VISU_WIDTH = 600;
    public static int INTERSECT_PRECISION = 2;	// intersect precision
    public static double ANGLE_PRECISION = Math.PI / 360.;	// when looking for closest crash obstacle
    public static int POINT_RADIUS = 200;		// radius of a simple point
    public static int ROBOT_RADIUS = 25;
}

class Obstacle {

    boolean _isWall = false;		// is it the wall obstacle?
    int _num_vertices = 0;			// number of vertices
    LinkedList<Point2D> points = new LinkedList<Point2D>();		// points
    LinkedList<Point2D> points_ext = new LinkedList<Point2D>();
    Polygon poly = new Polygon();	// polygon, should be clockwise
    Polygon poly_ext;
    Polygon poly_ext2;
    boolean _lock = false;			// lock

    // constructors
    public Obstacle(int num_vertices){
    	_num_vertices = num_vertices;
    }

    public Obstacle(int num_vertices, boolean isWall){
    	_num_vertices = num_vertices;
    	_isWall = isWall;
    }


    // add point
    public void addVertice (double cX, double cY){
    	if (_lock)
    		try_unlock();
    	else
    		points.add(new Point2D.Double(cX,cY));
    }


    // lock, obstacle won't change
    // we compute some infos about it
    public void lock(){
    	if (_lock) return;
    	// create polygon
    	for (int k = 0; k < points.size(); k++)
    		poly.addPoint((int)points.get(k).getX(),(int)points.get(k).getY());
    	poly = PolyOps.make_clockwise(poly);
    	// expanded polygon
    	if (Global.SAFETY_MARGIN != 0)
    		poly_ext = PolyOps.make_clockwise( PolyOps.expand(poly,Global.SAFETY_MARGIN) );
    	else
    		poly_ext = poly;
    	double extra_safety = Global.SAFETY_MARGIN2;
    	if (! isWall())
    		poly_ext2 = PolyOps.make_clockwise( PolyOps.expand(poly,Global.SAFETY_MARGIN+extra_safety) );
    	else poly_ext2 = PolyOps.make_clockwise( PolyOps.expand(poly,extra_safety) );
    }

    // error message if we try to do a locked operation
    void try_unlock() {
    	System.out.println("illegal operation: obstacle locked");
    }

    
    // returns points of poly_ext2
    LinkedList<Point2D> possiblePathPoints(){
    	LinkedList<Point2D> res = new LinkedList<Point2D>();
    	// special case, just return point of poly
    	if (isWall()) {
    		for (int k = 0; k < getPoly().npoints; k++){
    			Point2D p= new Point2D.Double(getPoly().xpoints[k],getPoly().ypoints[k]);
    			res.add(p);
    		} 
    		return res;
    	}
    	// normal case, use poly_ext2
    	for (int k = 0; k < getPolyExt2().npoints; k++){
    		Point2D p= new Point2D.Double(getPolyExt2().xpoints[k],getPolyExt2().ypoints[k]);
    		res.add(p);
	    }
    	return res;
    }

   

    // to handle special case of the wall
    // here we don't want to get out of poly
    // poly 2 is slightly expanded from poly in the wall case
    boolean exit_wall(double x1, double y1, double x2, double y2){
	//if (true) return false;
    	int delta = (int) Global.INTERSECT_PRECISION;
    	if (delta > Math.abs(x1 - x2) * 0.1)
    		delta = (int) (Math.abs(x1 - x2) * 0.1);
    	delta = Math.max(delta,1);
    	
    	// check extrema
    	if (!poly_ext2.contains(x1,y1))
    		return true;
    	if (!poly_ext2.contains(x2,y2))
    		return true;
    	// is segment vertical
    	if (x1 == x2) {
    		double y_small = Math.min(y1,y2);
    		double y_big = Math.max(y1,y2);
    		while (y_small + delta < y_big){
    			y_small += delta;
    			if ( !poly_ext2.contains(x1,y_small) )
    				return true;
    		}
    		return false;
    	}
    	// find function y = ax + b
    	double a, b;
    	if (x1 < x2)
    		a = (y2 - y1) * 1. / (x2 - x1);
    	else 
    		a = (y1 - y2) * 1. / (x1 - x2);
    	b = y1 - a * x1;
    	double small_x = Math.min(x1,x2);
    	double big_x = Math.max(x1,x2);
    	while(small_x + delta < big_x){
    		small_x += delta;
    		if ( !poly_ext2.contains(small_x,a * small_x+b) )
    			return true;
	    }
    	return false;
    }

    // check if a line intersects with the extended polygon
    boolean intersect_ext(double x1, double y1, double x2, double y2){
    	// is wall? special case
    	if (isWall()) {
    		return exit_wall(x1,y1,x2,y2);
    	}

    	// check obvious cases
    	if (Math.max(x1,x2) < poly_ext.getBounds().getX())
    		return false;
    	if (Math.min(x1,x2) > poly_ext.getBounds().getX()+poly_ext.getBounds().getWidth())
    		return false;
    	if (Math.max(y1,y2) < poly_ext.getBounds().getY())
    		return false;
    	if (Math.min(y1,y2) > poly_ext.getBounds().getY()+poly_ext.getBounds().getHeight())
    		return false;
    	// check extrema
    	if (poly_ext.contains(x1,y1))
    		return true;
    	if (poly_ext.contains(x2,y2))
    		return true;

    	// check every segment
    	double[] newseg = {x1,y1,x2,y2};
    	for (int p = 0; p < this.poly_ext.npoints; p++)
    	{
    		int p2 = p + 1;
    		if (p2 == poly_ext.npoints)
    			p2 = 0;
    		double[] seg = new double[4];
    		seg[0] = poly_ext.xpoints[p];
    		seg[1] = poly_ext.ypoints[p];
    		seg[2] = poly_ext.xpoints[p2];
    		seg[3] = poly_ext.ypoints[p2];
    		
    		if (Line2D.linesIntersect(newseg[0],newseg[1],newseg[2],newseg[3],seg[0],seg[1],seg[2],seg[3]))
    			return true;
    	}
    	return false;
    }


    // getters & setters
    boolean isWall() { return _isWall; }
    
    void setWall(boolean isWall) { 
    	if (!_lock) _isWall = isWall;
    	else try_unlock();
    }
    
    int numVertices() { return _num_vertices; }
    
    Polygon getPoly() {
    	if (!_lock) return poly;
    	else { try_unlock(); return null; }
    }
    
    Polygon getPolyExt() {
    	if (!_lock) return poly_ext;
    	else { try_unlock(); return null; }
    }
    
    Polygon getPolyExt2() {
    	if (!_lock) return poly_ext2;
    	else { try_unlock(); return null; }
    }
    // number of points of poly
    int size() {
	if (!_lock) return poly.npoints;
	else { try_unlock(); return -1; }
    }


    // utility functions
    public String toString() {
    	String s = "Obstacle";
    	if (isWall())
    		s+= "(Wall)";
    	s += ",s="+((Integer)numVertices()).toString() + "[";
    	for (int k = 0; k < numVertices(); k++){
    		s += ((Double) points.get(k).getX() ).toString();
    		s += "," + ((Double) points.get(k).getY() ).toString();
    		if (k + 1 < numVertices())
    			s += ";";
	    }
    	s += "]";
    	return s;
    }
}